|
In graph theory, a biconnected graph is a connected and "nonseparable" graph, meaning that if any vertex were to be removed, the graph will remain connected. Therefore a biconnected graph has no articulation vertices. The property of being 2-connected is equivalent to biconnectivity, with the caveat that the complete graph of two vertices is sometimes regarded as biconnected but not 2-connected. This property is especially useful in maintaining a graph with a two-fold redundancy, to prevent disconnection upon the removal of a single edge (or connection). The use of biconnected graphs is very important in the field of networking (see Network flow), because of this property of redundancy. == Definition == A biconnected undirected graph is a connected graph that is not broken into disconnected pieces by deleting any single vertex (and its incident edges). A biconnected directed graph is one such that for any two vertices ''v'' and ''w'' there are two directed paths from ''v'' to ''w'' which have no vertices in common other than ''v'' and ''w''. 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「Biconnected graph」の詳細全文を読む スポンサード リンク
|